package com.hy.dp.bagProblem.raidHomes;

import com.hy.treeNode.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class PlunderHouses03 {

    /**
     * 337.打家劫舍 III
     * 力扣题目链接
     *
     * 在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
     *
     * 计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
     * 思路
     * 这道题目和 198.打家劫舍，213.打家劫舍II也是如出一辙，只不过这个换成了树。
     * 动态规划
     * 在上面两种方法，其实对一个节点 偷与不偷得到的最大金钱都没有做记录，而是需要实时计算。
     *
     * 而动态规划其实就是使用状态转移容器来记录状态的变化，这里可以使用一个长度为2的数组，记录当前节点偷与不偷所得到的的最大金钱。
     *
     * 这道题目算是树形dp的入门题目，因为是在树上进行状态转移，我们在讲解二叉树的时候说过递归三部曲，那么下面我以递归三部曲为框架，其中融合动规五部曲的内容来进行讲解。
     *
     * 1.确定递归函数的参数和返回值
     * 这里我们要求一个节点 偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组。
     *
     * 参数为当前节点，代码如下：
     *
     * 其实这里的返回数组就是dp数组。
     *
     * 所以dp数组（dp table）以及下标的含义：下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。
     *
     * 所以本题dp数组就是一个长度为2的数组！
     *
     * 那么有同学可能疑惑，长度为2的数组怎么标记树中每个节点的状态呢？
     *
     * 别忘了在递归的过程中，系统栈会保存每一层递归的参数。
     *
     * 2.确定终止条件
     * 在遍历的过程中，如果遇到空节点的话，很明显，无论偷还是不偷都是0，所以就返回
     *
     * 3.确定遍历顺序
     * 首先明确的是使用后序遍历。 因为通过递归函数的返回值来做下一步计算。
     *
     * 通过递归左节点，得到左节点偷与不偷的金钱。
     *
     * 通过递归右节点，得到右节点偷与不偷的金钱。
     *
     * 4.确定单层递归的逻辑
     * 如果是偷当前节点，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0]; （如果对下标含义不理解就在回顾一下dp数组的含义）
     *
     * 如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);
     *
     * 最后当前节点的状态就是{val2, val1}; 即：{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱}
     *
     * 5.举例推导dp数组
     * 以示例1为例，dp数组状态如下：（注意用后序遍历的方式推导）
     *
     * @return
     */
    // 3.状态标记递归
    // 执行用时：0 ms , 在所有 Java 提交中击败了 100% 的用户
    // 不偷：Max(左孩子不偷，左孩子偷) + Max(又孩子不偷，右孩子偷)
    // root[0] = Math.max(rob(root.left)[0], rob(root.left)[1]) +
    // Math.max(rob(root.right)[0], rob(root.right)[1])
    // 偷：左孩子不偷+ 右孩子不偷 + 当前节点偷
    // root[1] = rob(root.left)[0] + rob(root.right)[0] + root.val;
    public static int plunderHouses03(TreeNode root) {
        int[] res = robAction1(root);
        return Math.max(res[0],res[1]);
    }

    public static int[] robAction1(TreeNode root){
        //1.确定递归函数的参数和返回值
        int [] res = new int[2];
        //2. 确定终止条件
        if (root == null){
            return res;
        }
        //3.确定遍历顺序
        //首先明确的是使用后序遍历。 因为通过递归函数的返回值来做下一步计算。
        //通过递归左节点，得到左节点偷与不偷的金钱。
        //通过递归右节点，得到右节点偷与不偷的金钱。
        int [] left = robAction1(root.left);
        int [] right =robAction1(root.right);
        // 不偷当前节点，那么可以偷也可以不偷左右节点，则取较大的情况
        res[0] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);
        // 偷当前节点，那么就不能偷左右节点。
        res[1] = root.val + left[0] + right[0];
        return res;
    }

    // 2.递归去偷，记录状态
    // 执行用时：3 ms , 在所有 Java 提交中击败了 56.24% 的用户

    public static int plunderHouses04(TreeNode root){
        Map<TreeNode,Integer> param = new HashMap<>();
        return robAction(root,param);
    }

    public static int robAction(TreeNode root, Map<TreeNode,Integer> memo){
        if (root == null){
            return 0;
        }
        if (memo.containsKey(root)){
            return memo.get(root);
        }
        int val = root.val;
        if (root.left != null){
            val += robAction(root.left.left,memo) + robAction(root.left.right,memo);
        }
        if (root.right != null){
            val += robAction(root.right.left,memo) + robAction(root.right.right,memo);
        }
        int res = Math.max(val,robAction(root.left,memo) + robAction(root.right,memo));
        memo.put(root,res);
        return res;
    }

    public static void main(String[] args) {
        TreeNode leftNode1 = new TreeNode(1, null, null);
        TreeNode rightNode1 = new TreeNode(2, null, null);

        TreeNode leftNode2 = new TreeNode(6, null, null);
        TreeNode rightNode2 = new TreeNode(8, null, null);

        TreeNode leftNode = new TreeNode(4, leftNode1, rightNode1);
        TreeNode rightNode = new TreeNode(7, leftNode2, rightNode2);

        TreeNode root = new TreeNode(5, leftNode, rightNode);

        System.out.println("res: "+plunderHouses04(root));
        System.out.println("res: "+plunderHouses03(root));

    }
}
